from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if (len(nums) == 0):
            return -1
        return self.searchPart(nums, target, 0, len(nums))

    def searchPart(self, nums: List[int], target: int, s: int, e: int) -> int:
        if e - s <= 4:
            for i in range(s, e):
                if nums[i] == target:
                    return i
            return -1

        mid = (e - s) // 2 + s
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            return self.searchPart(nums, target, s, mid)
        else:
            return self.searchPart(nums, target, mid + 1, e)


solu = Solution()
# print(solu.search(nums = [-1,0,3,5,9,12], target = 9))
# print(solu.search(nums = [-1,0,3,5,9,12], target = 13))
print(solu.search(nums=[2, 5], target=5))
